#include "main/utils.h"
using namespace std;

int min(vector<int> vec_tmp, int &idx2, int &idx3, int &idx5) {
  int mul2 = vec_tmp[idx2] * 2;
  int mul3 = vec_tmp[idx3] * 3;
  int mul5 = vec_tmp[idx5] * 5;
  int ret = 0;
  if (mul2 <= mul3 && mul2 <= mul5) {
    ret = mul2;
  } else if (mul3 <= mul5) {
    ret = mul3;
  } else {
    ret = mul5;
  }
  return ret;
}

int kthUglyNum(int kth) {
  vector<int> vec_tmp{1};
  int idx2 = 0, idx3 = 0, idx5 = 0;
  int cur_max = 1;
  while (vec_tmp.size() < kth) {
    cur_max = min(vec_tmp, idx2, idx3, idx5);
    vec_tmp.push_back(cur_max);
    while (vec_tmp[idx2] * 2 <= cur_max)
      ++idx2;
    while (vec_tmp[idx3] * 3 <= cur_max)
      ++idx3;
    while (vec_tmp[idx5] * 5 <= cur_max)
      ++idx5;
  }
  return vec_tmp[kth - 1];
}

int main() {
  int kth = 1500;
  int ret = kthUglyNum(kth);
  cout << "The 1500th ugly number is: " << ret << endl;

  return 0;
}
